package BFS解决FloodFill算法.多源;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class 地图分析 {
    int [] dx = {0,0,1,-1};
    int [] dy = {1,-1,0,0};

    public int maxDistance(int[][] grid) {

        int m = grid.length;
        int n = grid[0].length;

        Queue<int []> q = new LinkedList<>();
        int [] [] dist = new int[m][n];
        for(int i = 0;i<m;i++)
            for(int j = 0 ; j<n;j++)
                dist[i][j] = -1;
        // 1.进行边界为 1的预处理
        for(int i = 0;i<m;i++)
        {
            for(int j = 0;j<n;j++)
            {
                if(grid[i][j] == 1)
                {
                    dist[i][j] = 0;
                    q.add(new int []{i,j});
                }
            }
        }


        int ret = -1;
        while(!q.isEmpty())
        {
            int [] cur = q.poll();
            int a=  cur[0],b= cur[1];
            for(int i = 0 ;i<4;i++)
            {
                int x = a + dx[i];
                int y = b + dy[i];

                if(x>=0 && x<m && y>=0 && y<n && dist[x][y] == -1)
                {
                    dist[x][y] = dist[a][b] + 1;
                    ret = Math.max(ret,dist[x][y]);
                    q.add(new int []{x,y});
                }
            }

        }
        return ret;
    }
}
